package Test;

public class Test02 {
    /**
     * 合并两个有序链表 并返回一个升序链表
     * 定义一个虚拟节点newHead , 再定义一个tmp 来代表 newHead 遍历链表
     * 当head1 和 head2 都不为空时 , 如果 head1 < head2 的值 将head1的值给tmp.next,然后head1往后走 head1=head1.next. tmp也往后走
     * else 如果 head1 > head2的值, 将head2的值给 tmp.next,head2往后走 head2 = head2.next. tmp 也往后走
     * 如果 head1不为空时 , tmp.next = head1
     * 如果 head2不为空时 , tmp.next = head2
     * 最后返回 newHead.next
     */
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;

        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(10);
        mySingleList.addLast(15);
        mySingleList.addLast(30);
        mySingleList.addLast(32);

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(4);
        mySingleList2.addLast(14);
        mySingleList2.addLast(16);
        mySingleList2.addLast(21);
        mySingleList.display();
        mySingleList2.display();
        System.out.println("===============");
        MySingleList.ListNode ret = mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList2.display(ret);
    }
}
